স্ট্রিং অ্যালগরিদম (String Algorithms)

স্ট্রিং অ্যালগরিদমগুলি স্ট্রিং বা অক্ষর সিকোয়েন্সের সাথে সম্পর্কিত বিভিন্ন সমস্যার সমাধানের জন্য ব্যবহৃত হয়। এই অ্যালগরিদমগুলি স্ট্রিং ম্যানিপুলেশন, সার্চিং, কম্পারিজন এবং পার্সিং এর জন্য কার্যকরী। স্ট্রিং অ্যালগরিদমগুলি কম্পিউটার সায়েন্সে একটি গুরুত্বপূর্ণ অংশ, বিশেষ করে টেক্সট প্রসেসিং, ডেটা সংরক্ষণ এবং কম্পাইলার ডিজাইনে।

স্ট্রিং অ্যালগরিদমের প্রধান ধরনগুলি:

১. স্ট্রিং সার্চিং অ্যালগরিদম

ব্রুট ফোর্স সার্চ (Brute Force Search): একটি স্ট্রিংয়ে একটি সাবস্ট্রিং খুঁজে বের করার সহজতম পদ্ধতি। এটি মূল স্ট্রিংয়ের প্রতিটি অবস্থান থেকে সাবস্ট্রিংটির সাথে তুলনা করে।

টাইম কমপ্লেক্সিটি: O(m * n), যেখানে m হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং n হল সাবস্ট্রিংয়ের দৈর্ঘ্য।

def brute_force_search(text, pattern):
    n = len(text)
    m = len(pattern)
    
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i  # Return the starting index
    return -1  # If not found

text = "hello world"
pattern = "world"
print(brute_force_search(text, pattern))  # Output: 6

কনফ্লিক্ট টেবিল (KMP Algorithm): Knuth-Morris-Pratt অ্যালগরিদম একটি উন্নত পদ্ধতি যা সাবস্ট্রিং খোঁজার সময় অপ্রয়োজনীয় তুলনা এড়ায়। এটি একটি "লং ফাংশন" (lps array) তৈরি করে যা ডেটা সার্চ করতে সাহায্য করে।

টাইম কমপ্লেক্সিটি: O(m + n)

def kmp_search(text, pattern):
    def build_lps(pattern):
        lps = [0] * len(pattern)
        j = 0
        for i in range(1, len(pattern)):
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
                lps[i] = j
        return lps

    lps = build_lps(pattern)
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            j += 1
            if j == len(pattern):
                return i - j + 1
    return -1

text = "hello world"
pattern = "world"
print(kmp_search(text, pattern))  # Output: 6

২. স্ট্রিং ম্যানিপুলেশন অ্যালগরিদম

• রিভার্সিং এ স্ট্রিং: একটি স্ট্রিংকে বিপরীত করতে ব্যবহৃত হয়। এটি বিভিন্ন অ্যাপ্লিকেশনে প্রয়োজন হতে পারে।

def reverse_string(s):
    return s[::-1]

text = "hello"
print(reverse_string(text))  # Output: "olleh"

• স্ট্রিং কনক্যাটেনেশন: দুটি স্ট্রিংকে একত্রিত করা। বিভিন্ন পরিস্থিতিতে এটি ব্যবহৃত হয়।

def concatenate_strings(s1, s2):
    return s1 + s2

text1 = "hello"
text2 = " world"
print(concatenate_strings(text1, text2))  # Output: "hello world"

৩. স্ট্রিং কম্পারিজন অ্যালগরিদম

• লেক্সিকোগ্রাফিক কম্পারিজন: দুটি স্ট্রিংয়ের তুলনা করা যাতে এটি নির্ধারণ করা যায় কোনটি প্রথম আসে। এটি আলফাবেটিক্যাল অর্ডারে হয়।

def lexicographic_comparison(s1, s2):
    if s1 < s2:
        return -1
    elif s1 > s2:
        return 1
    return 0

print(lexicographic_comparison("apple", "banana"))  # Output: -1

৪. স্ট্রিং ম্যানিপুলেশন টেকনিকস

• রেগুলার এক্সপ্রেশন (Regular Expressions): স্ট্রিংে নির্দিষ্ট প্যাটার্ন খুঁজতে এবং ম্যানিপুলেট করতে ব্যবহৃত হয়। এটি অত্যন্ত শক্তিশালী এবং বিভিন্ন ভাষায় পাওয়া যায়।

import re

def find_pattern_in_text(text, pattern):
    return re.findall(pattern, text)

text = "hello world, hello universe"
pattern = "hello"
print(find_pattern_in_text(text, pattern))  # Output: ['hello', 'hello']

স্ট্রিং অ্যালগরিদমের অ্যাপ্লিকেশন

1. টেক্সট প্রসেসিং: শব্দের প্রক্রিয়াকরণ এবং বিভিন্ন টেক্সট ফাইল বিশ্লেষণে।
2. ডেটাবেস: স্ট্রিং সার্চিং এবং ডেটাবেসে প্রশ্ন তৈরি করার সময়।
3. কম্পাইলার ডিজাইন: লেক্সার এবং সিনট্যাক্স বিশ্লেষণে স্ট্রিং ম্যানিপুলেশন।
4. নেটওয়ার্ক প্রোটোকল: স্ট্রিং ব্যবহার করে ডেটা বিনিময়ের সময়।

উপসংহার

স্ট্রিং অ্যালগরিদমগুলি কম্পিউটার সায়েন্সে একটি গুরুত্বপূর্ণ স্থান অধিকার করে এবং বিভিন্ন সমস্যা সমাধানে প্রয়োগ করা হয়। সঠিক অ্যালগরিদম নির্বাচন করা সমস্যার ধরণ এবং আকারের উপর নির্ভর করে। আধুনিক ডেটা বিশ্লেষণ এবং তথ্য পরিচালনায় স্ট্রিং অ্যালগরিদমগুলি অত্যন্ত কার্যকর।

স্ট্রিং ম্যাচিং অ্যালগরিদমগুলি টেক্সটের মধ্যে একটি নির্দিষ্ট প্যাটার্ন খুঁজে বের করার জন্য ব্যবহৃত হয়। দুটি জনপ্রিয় স্ট্রিং ম্যাচিং অ্যালগরিদম হলো Naive String Matching Algorithm এবং KMP (Knuth-Morris-Pratt) Algorithm। এগুলি তাদের কার্যপদ্ধতি এবং কার্যক্ষমতার জন্য বিশেষভাবে পরিচিত।

১. Naive String Matching Algorithm

Naive String Matching Algorithm হল একটি সরল এবং সহজ স্ট্রিং ম্যাচিং পদ্ধতি। এই পদ্ধতিতে প্যাটার্নটি টেক্সটের প্রতিটি সম্ভাব্য অবস্থানে পরীক্ষা করা হয়।

কাজের প্রক্রিয়া:

1. টেক্সটের প্রতিটি অবস্থান থেকে প্যাটার্নের প্রথম অক্ষর শুরু করে পরীক্ষা করা হয়।
2. যদি প্রথম অক্ষরটি মেলে, তবে পরবর্তী অক্ষরগুলোর জন্য পরীক্ষা চালানো হয়।
3. যদি পুরো প্যাটার্নটি মিলে যায়, তবে প্যাটার্নের সূচক (অবস্থান) রিটার্ন করা হয়।
4. এই প্রক্রিয়াটি টেক্সটের শেষ পর্যন্ত চলতে থাকে।

টাইম কমপ্লেক্সিটি:

• Worst Case: O(n * m), যেখানে nn হল টেক্সটের দৈর্ঘ্য এবং mm হল প্যাটার্নের দৈর্ঘ্য।

উদাহরণ কোড:

def naive_string_matching(text, pattern):
    n = len(text)
    m = len(pattern)

    for i in range(n - m + 1):  # Move the pattern across the text
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:  # Found the pattern
            print(f"Pattern found at index {i}")

# Example usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
naive_string_matching(text, pattern)

২. KMP Algorithm

KMP Algorithm একটি উন্নত স্ট্রিং ম্যাচিং অ্যালগরিদম যা প্যাটার্নের আংশিক মেলানো তথ্য ব্যবহার করে যাতে পুনরায় ম্যাচিং করার প্রয়োজনীয়তা কমে যায়। এটি প্রতি অক্ষর পুনরায় পরীক্ষা না করেই টেক্সট এবং প্যাটার্নের মধ্যে মেলানো খুঁজে বের করতে সক্ষম।

কাজের প্রক্রিয়া:

1. প্রিপ্রসেসিং (Preprocessing): একটি লংজিটুডিনাল অ্যারে (LPS Array) তৈরি করা হয়, যা প্যাটার্নের প্রতিটি অক্ষরের জন্য আংশিক মেলানো তথ্য সংরক্ষণ করে। এই LPS অ্যারে প্যাটার্নের এক অংশের অক্ষরগুলোর মধ্যে সঙ্গতিপূর্ণ উপসেট নির্দেশ করে।
2. ম্যাচিং (Matching): টেক্সটের অক্ষরগুলোর সাথে প্যাটার্নের অক্ষর তুলনা করা হয়। যদি অক্ষর মেলে, তাহলে উভয় সূচক বাড়ানো হয়। যদি না মেলে, তাহলে LPS অ্যারেকে ব্যবহার করে প্যাটার্নের সূচকটি আপডেট করা হয়।

টাইম কমপ্লেক্সিটি:

• O(n + m), যেখানে nn হল টেক্সটের দৈর্ঘ্য এবং mm হল প্যাটার্নের দৈর্ঘ্য।

উদাহরণ কোড:

def KMPSearch(text, pattern):
    m = len(pattern)
    n = len(text)

    # Create LPS array
    lps = [0] * m
    j = 0  # Length of previous longest prefix suffix
    computeLPSArray(pattern, m, lps)

    i = 0  # Index for text
    while n - i >= m:  # Only check for matches if enough characters remain
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:  # Found the pattern
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]  # Use LPS to find next position
        elif i < n and pattern[j] != text[i]:  # Mismatch after j matches
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

def computeLPSArray(pattern, m, lps):
    length = 0  # Length of the previous longest prefix suffix
    lps[0] = 0  # lps[0] is always 0
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

# Example usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
KMPSearch(text, pattern)

Naive vs KMP Algorithm

সারসংক্ষেপ

Naive String Matching Algorithm সরল কিন্তু অকার্যকর, যখন KMP Algorithm উন্নত এবং কার্যকর। KMP পদ্ধতি আংশিক মেলানো তথ্য ব্যবহার করে সময় সাশ্রয় করে এবং পুনরায় পরীক্ষা করা প্রয়োজনীয়তা কমিয়ে আনে। বিভিন্ন স্ট্রিং ম্যাচিং সমস্যায় KMP Algorithm আরও কার্যকরী।

বর্নী স্ট্রিং সমস্যা হলো স্ট্রিং থেকে বিভিন্ন উপাদান বা উপস্ট্রিং খোঁজার একটি ক্ষেত্র, যেখানে Suffix Tree এবং Suffix Array দুটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার।

১. Suffix Tree

Suffix Tree হলো একটি বিশেষ গাছের গঠন যা একটি স্ট্রিংয়ের সমস্ত সম্ভাব্য suffix (শেষাংশ) গুলি ধারণ করে। এটি একটি ট্রাই ধরনের ডেটা স্ট্রাকচার যেখানে প্রতিটি পাতা একটি suffix উপস্থাপন করে।

বৈশিষ্ট্য:

• O(n) সময়ে স্ট্রিংয়ের সকল suffix তৈরি করা যায়।
• অনুসন্ধান করা এবং substring matching করার জন্য খুবই কার্যকর।
• সংক্ষেপিত এবং স্মৃতি দক্ষ।

Suffix Tree তৈরি করার জন্য অ্যালগরিদম:

Suffix Tree নির্মাণের জন্য Ukkonen's Algorithm ব্যবহৃত হয়, যা O(n)O(n) সময়ে গাছ তৈরি করতে সক্ষম।

উদাহরণ (Python Implementation):

class SuffixTreeNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class SuffixTree:
    def __init__(self, text):
        self.root = SuffixTreeNode()
        self.build_suffix_tree(text)

    def build_suffix_tree(self, text):
        for i in range(len(text)):
            self.insert_suffix(text[i:])

    def insert_suffix(self, suffix):
        node = self.root
        for char in suffix:
            if char not in node.children:
                node.children[char] = SuffixTreeNode()
            node = node.children[char]
        node.is_end = True

    def search(self, pattern):
        node = self.root
        for char in pattern:
            if char not in node.children:
                return False
            node = node.children[char]
        return True if node.is_end else False

# উদাহরণ ব্যবহার
text = "banana"
suffix_tree = SuffixTree(text)
print("Searching for 'ana':", suffix_tree.search('ana'))
print("Searching for 'nan':", suffix_tree.search('nan'))

২. Suffix Array

Suffix Array হলো একটি sorted array যা একটি স্ট্রিংয়ের সকল suffix এর সূচক ধারণ করে। এটি Suffix Tree- এর তুলনায় অনেক বেশি স্থান অর্থনৈতিক এবং সহজে তৈরি করা যায়।

বৈশিষ্ট্য:

• Suffix Array স্ট্রিংটির প্রস্থ বাড়ানোর জন্য স্মৃতির প্রয়োজনীয়তা কমায়।
• এটি সাধারণত একটি সাঁকোডেড গাছের সাথে ব্যবহৃত হয় যা substring অনুসন্ধানের জন্য দ্রুত।

Suffix Array তৈরি করার জন্য অ্যালগরিদম:

Suffix Array নির্মাণের জন্য কয়েকটি অ্যালগরিদম আছে, যেমন:

1. Naive Approach: O(n^2 log n) সময়ের মধ্যে তৈরি করা হয়।
2. O(n log n) এবং O(n) টাইম অ্যালগরিদম।

উদাহরণ (Python Implementation):

def build_suffix_array(text):
    suffixes = [(text[i:], i) for i in range(len(text))]
    suffixes.sort()  # Sort the suffixes
    return [suffix[1] for suffix in suffixes]

# উদাহরণ ব্যবহার
text = "banana"
suffix_array = build_suffix_array(text)
print("Suffix Array:", suffix_array)

সারসংক্ষেপ

Suffix Tree:

• একটি গাছের গঠন যা স্ট্রিংয়ের সমস্ত suffix ধারণ করে।
• substring matching এবং অনুসন্ধানের জন্য কার্যকর।
• O(n) সময়ে তৈরি করা যায়।

Suffix Array:

• একটি sorted array যা suffix এর সূচক ধারণ করে।
• Suffix Tree এর তুলনায় স্থান সংরক্ষণ করে।
• সাধারণভাবে O(n log n) বা O(n) সময়ে তৈরি করা যায়।

Suffix Tree এবং Suffix Array উভয়ই টেক্সট প্রক্রিয়াকরণ, কম্পিউটেশনাল বায়োলজি এবং ডেটা কম্প্রেশন সহ বিভিন্ন ক্ষেত্রে ব্যবহার করা হয়। 

রাবিন-কার্প অ্যালগরিদম (Rabin-Karp Algorithm) একটি স্ট্রিং মেচিং অ্যালগরিদম যা প্যাটার্নের খোঁজ করার জন্য হ্যাশিং প্রযুক্তি ব্যবহার করে। এটি বিশেষ করে অনেকগুলো প্যাটার্নের জন্য একটি টেক্সটে খোঁজার ক্ষেত্রে কার্যকর।

অ্যালগরিদমের মূলনীতি

রাবিন-কার্প অ্যালগরিদম মূলত দুটি ধাপে কাজ করে:

হ্যাশিং: টেক্সট এবং প্যাটার্ন উভয়ের জন্য একটি হ্যাশ ফাংশন ব্যবহার করে একটি নির্দিষ্ট সংখ্যা (হ্যাশ ভ্যালু) তৈরি করে। এটি প্যাটার্নের দৈর্ঘ্যের উপর ভিত্তি করে টেক্সটের অংশগুলির জন্যও হ্যাশ ফাংশন তৈরি করে।

মেলানো: হ্যাশ ভ্যালুগুলি তুলনা করে, যদি দুইটি হ্যাশ ভ্যালু সমান হয় তবে স্ট্রিংগুলির সত্যিকার মিল যাচাই করতে হবে। কারণ হ্যাশিং এ সম্ভাব্য সংঘর্ষ ঘটতে পারে, তাই নিশ্চিতকরণের জন্য স্ট্রিংগুলি তুলনা করা হয়।

অ্যালগরিদমের প্রক্রিয়া

প্রাথমিককরণ:

• প্যাটার্নের এবং টেক্সটের প্রথম \( m \) (প্যাটার্নের দৈর্ঘ্য) চরিত্রের জন্য হ্যাশ ভ্যালু তৈরি করুন।

স্লাইডিং উইন্ডো:

• টেক্সটের উপর প্যাটার্নের হ্যাশ ভ্যালুর সাথে তুলনা করুন। যদি সমান হয়, তাহলে প্যাটার্নটি পাওয়া গেছে।
• যদি হ্যাশ ভ্যালুগুলি সমান হয়, তখন চরিত্রগুলি পরীক্ষা করুন (কারণ হ্যাশিং এ সংঘর্ষ হতে পারে)।

হ্যাশ আপডেট:

• পরবর্তী চরিত্রে স্লাইড করার জন্য হ্যাশ ভ্যালু আপডেট করুন। নতুন হ্যাশ ভ্যালু গণনা করতে পুরনো হ্যাশ ভ্যালু থেকে প্রথম চরিত্রটি বাদ দিন এবং নতুন চরিত্রটি যোগ করুন।

টাইম কমপ্লেক্সিটি

- গড় ক্ষেত্রে, সময় জটিলতা \( O(n + m) \) যেখানে \( n \) হল টেক্সটের দৈর্ঘ্য এবং \( m \) হল প্যাটার্নের দৈর্ঘ্য। তবে খারাপ ক্ষেত্রে \( O(nm) \) হতে পারে।

উদাহরণ

ধরি আমাদের টেক্সট "ABABDABACDABABCABAB" এবং প্যাটার্ন "ABABCABAB"।

1. প্যাটার্নের জন্য হ্যাশ ভ্যালু গণনা করুন।
2. টেক্সটের প্রথম 9টি চরিত্রের জন্য হ্যাশ ভ্যালু তৈরি করুন।
3. এটি টেক্সটের মধ্যে স্লাইড করে যান এবং হ্যাশ ভ্যালুগুলি তুলনা করুন।

প্রয়োগ

রাবিন-কার্প অ্যালগরিদমের কিছু প্রধান প্রয়োগ হল:

স্ট্রিং অনুসন্ধান: বড় টেক্সটে একটি নির্দিষ্ট স্ট্রিং খুঁজতে ব্যবহৃত হয়, যেমন ডেটাবেস প্রশ্ন বা পাঠ্য সম্পাদক।

জেনারেটিভ এপ্লিকেশন: যেমন, ডেটা মাইনিং এ, যেখানে একই প্যাটার্ন পুনরাবৃত্তি খুঁজতে হয়।

প্যাটার্ন ম্যাচিং: অ্যালগরিদমের গতি এবং কার্যকারিতা নিশ্চিত করার জন্য বিগ ডেটা বিশ্লেষণে।

পাঠ্য এডিটিং টুলস: যেমন, টেক্সট এডিটর যেখানে ব্যবহারকারীরা দ্রুত স্ট্রিং খোঁজার জন্য অ্যালগরিদম ব্যবহার করে।

উপসংহার

রাবিন-কার্প অ্যালগরিদম একটি শক্তিশালী এবং কার্যকরী স্ট্রিং মেচিং অ্যালগরিদম যা বিশেষত হ্যাশিংয়ের সুবিধা ব্যবহার করে। এটি বিভিন্ন ক্ষেত্রে, বিশেষ করে যেখানে অনেক প্যাটার্নের সাথে কাজ করতে হয়, অত্যন্ত উপকারী।